#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN=1050;
const int INF=10000007;
int d[MAXN];
int g[MAXN];
int main(void){
	int a[]={1,2,2,2,2,2};
	int n=6;
	/*
	 * O(n^2)算法
	 * 状态转移公式：d[i]=max(d[j],0)+1 (j<i && a[j]<a[i])
	d[0]=1;
	for(int i=1;i<n;i++){
		for(int j=0;j<i;j++){
			if(a[j]<a[i]){
				d[i]=max(d[j],0)+1;
			}
		}
	}
	for(int i=0;i<n;i++){
		printf("%d ",d[i]);
	}
	printf("\n");
	*/
	/*
	 * O(nlogn)算法
	 * g数组表示长度为g[i]的自序列的最小(最前)的那个数
	 */
	for(int i=1;i<=n;i++){
		g[i]=INF;
	}
	//记好这几步操作
	for(int i=0;i<n;i++){
		int k=lower_bound(g+1,g+n,a[i])-g;
		d[i]=k;
		g[k]=a[i];
	}
	for(int i=0;i<n;i++){
		printf("%d ",d[i]);
	}
	printf("\n");
	for(int i=1;i<=n;i++){
		printf("%d ",g[i]);
	}
	printf("\n");
	return 0;
}
